package com.ztom.top100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 找到所有数组中消失的数字
 * <p>
 * https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
 *
 * @author ZhangTao
 */
public class Code90FindDisappearedNumbers {

    public List<Integer> findDisappearedNumbers2(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, num);
        }
        for (int i = 1; i <= n; i++) {
            if (!map.containsKey(i)) {
                res.add(i);
            }
        }

        return res;
    }

    /**
     * 范围已知 [1,n], 可以用数组优化 map
     *
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        // 出现过的数, 将数值对应的 index 位置的数修改为相反数
        // 如果存在位置任然大于 0 就是消失的数字
        for (int i = 0; i < nums.length; i++) {
            // 当前位置的数, 需要取绝对值获取到原数值
            int iNum = Math.abs(nums[i]);
            // 对应 index 位置的数
            int tNum = nums[iNum - 1];
            // 修改为相反数
            nums[iNum - 1] = -Math.abs(tNum);
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                res.add(i + 1);
            }
        }

        return res;
    }

    /**
     * 位运算优化
     *
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        int n = nums.length;
        for (int num : nums) {
            // 取出原来的数值
            int x = (num - 1) % n;
            // 修改对应位置的数
            nums[x] += n;
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= n) {
                res.add(i + 1);
            }
        }

        return res;
    }
}
